/**
    算法描述：
    核心问题：
    解决所需数据结构+算法：
**/
#include<cstdio>
#include<stack>
#include<cstring>
using namespace std;
  
struct edge {
    int x, y, pre;
}a[50010];
int alen, last[20010];
  
void ins(int x, int y) {
    a[++alen] = edge{x, y, last[x]};
    last[x] = alen;
}
  
int max(int x, int y) {
    return x > y ? x : y;
}
  
stack<int> st;
bool v[20010] = {false};
int idx[20010], db[20010], rd[20010], cd[20010], stddb[20010];
int id = 0, ans = 0;
  
void dfs(int x) {
    idx[x] = db[x] = ++id;
    st.push(x);
    v[x] = true;
    for (int k=last[x]; k; k=a[k].pre) {
        int y = a[k].y;
        if (!idx[y]) {
            dfs(y);
            db[x] = min(db[x], db[y]);
        } else {
            if (v[y]) {
                db[x] = min(db[x], db[y]);
            }
        }
    }
  
    if (idx[x] == db[x]) {
        ans++;
        int y;
        do{
            y = st.top();
            st.pop();
            stddb[y] = ans;
            v[y] = false;
        }while(x!=y);
    }
}
  
int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        memset(v, false, sizeof(v));
        memset(idx, 0, sizeof(idx));
        memset(db, 0, sizeof(db));
        memset(rd, 0, sizeof(rd));
        memset(cd, 0, sizeof(cd));
        memset(last, 0, sizeof(last));
        memset(stddb, 0, sizeof(stddb));
        alen = 0; id = 0; ans = 0;
        int n, m;
        int rr = 0, cc = 0;
        scanf("%d%d", &n ,&m);
        while(m--) {
            int x, y;
            scanf("%d%d", &x, &y);
            ins(x, y);
        }
        for (int i=1; i<=n; i++) {
            if (!idx[i]) {
                dfs(i);
            }
        }
        if (ans == 1) {
            printf("0\n");
            continue;
        }
        for (int i=1; i<=alen; i++) {
//          这里的rd、cd数组实际上存的是每个连通分量的入度出度值 ，因此下面 for 应该循环的是连通分量的数量
            int x = a[i].x;
            int y = a[i].y;
            if (stddb[x] != stddb[y]) {
                rd[stddb[x]]++;
                cd[stddb[y]]++;
            }
        }
        for (int i=1; i<=ans; i++) {
            if (rd[i] == 0)
                rr++;
            if (cd[i] == 0)
                cc++;
        }
        printf("%d\n", max(rr, cc));
    }
    return 0;
}